// https://www.lintcode.com/problem/find-minimum-in-rotated-sorted-array-ii/

public class Solution {
    /**
     * @param nums: a rotated sorted array
     * @return: the minimum number in the array
     */
    public int findMin(int[] nums) {
        // write your code here
        int start = 0;
        int end = nums.length - 1;
        while ((start < end) && (nums[start] >= nums[end])) { // 结果肯定在start和end中间某个位置
          int mid = (start + end) / 2;
          if (nums[start] < nums[mid]) { // mid在前半区间
            start = mid + 1;
          } else if (nums[start] > nums[mid]) {
            end = mid; // 不用减一，有可能就是这个位置。
          } else {
            ++start;
          }
        }
        return nums[start];
    }
}